Flash memory is a form of EEPROM (Electrically Erasable and Programmable Read Only Memory) that allows multiple memory locations to be erased or written in one programming operation. The memory is commonly used as a mass data storage subsystem for electronic devices, such as memory cards, USB (Universal Serial Bus) flash drives and solid-state drives as replacements of hard disk drives.
A flash memory device consists of one or more arrays of transistor cells as its data storage units. Each of those cells is capable of keeping one or more bits of data even if the electric power supply is cut off. Therefore, a flash memory is termed a non-volatile memory because it does not require an external power supply to retain stored data. However, this also requires that previously stored data is erased once a new round of programming or data input is required. This process is termed an erase-before-write, which is often time-consuming.
In commercial applications, a large number of transistor cells are divided into physical blocks, pages and sectors for their address management to facilitate data access, storage and programming. A flash memory is generally organized into a plurality of physical blocks. Each of these blocks is divided into a plurality of physical pages. Within each physical page, memory is often divided into two portions for the storage of user data and overhead data. Overhead data is commonly used to store the user data's status and flags, to record logical address information, error correction code, etc. Overhead data is sometimes also termed spare area or redundant data. FIG. 1 shows an example of a flash memory 5 having M blocks 50 (labeled 0 to M−1), each block 50 being organized into G pages 60 (labeled 0 to G−1), and each page 60 being further divided into user data 70 and overhead data 72 portions.
In one commercial implementation, a flash memory device consists of a number of blocks of 16 KB each. Every block is further divided into 32 pages, each page is then able to store 512 bytes of data equal to the size of a host sector. In another commercial implementation, a flash memory device consists of blocks of 128 KB each, a page size of 2 KB, such that a block is composed of 64 pages, and a page is composed of 4 sectors. In addition, each page also contains additional non-volatile cells for storing overhead data. These flash memory devices are herein termed multi-paged block flash memories, since every block is organized into a plurality of pages.
Programming flash memory is usually done in one or more pages, which is typically less than a block size. Moreover, in one commercial implementation (e.g., some NAND flash memories), pages within a block must be programmed in order from the least significant page to the most significant page. Random page programming within the block is prohibited.
To avoid the operation of erase-before-write, the concept of logical and physical addresses has been introduced. The physical address denotes the actual location or address of a group of transistor cells while the logical address means an address recognized by a host and which is logically associated to a physical address. A read/write operation for a logical address requested from a host end is converted into a read/write operation for an actual physical address of a flash memory by several steps of mapping algorithms. This mapping algorithm is often performed by a device termed a flash memory controller. The challenge for such a flash memory controller is how to optimize the flash memory controller system architecture to improve data access speed, to utilize the flash memory blocks and pages more efficiently and to improve on the reliability and usage life of the flash memories.
FIG. 2 shows a flash memory controller attached to the host at one interface and flash memories at another interface. The flash memory controller and its attached flash memories are semiconductor devices and they form a non-volatile semiconductor mass storage system together. FIG. 2 shows internal blocks of a typical flash memory controller with only major blocks shown for clarity. A host 1 communicates with a flash memory controller 3, which is arranged to access a non-volatile memory consisting of one or more physically-separate flash memory devices 5. The communication between the flash controller 3 and the host 1 is via a host interface 7. The communication between the controller 3 and the memory devices 5 is via a flash interface 9. The controller 3 further includes a ECC logic unit 13, a buffer RAM 11 and a processor 15. The processor 15 operates making use of temporary memory provided by a system volatile RAM 17 and a processor RAM 19, and software stored in a ROM 21.
In a typical process of operation for the device illustrated in FIG. 2, the host 1 initiates a data transfer operation by sending commands to the flash controller 3. A host write command specifies the starting logical address to write along with the number of sectors to write. A host read command specifies the starting logical address to read from along with the number of sectors to read.
User data is typically transferred between host and flash memories through the buffer RAM 11. The host uses logical addresses to read or write data. One of the functions of the controller 3 is to translate the host logical addresses into flash memory physical addresses so that data can be stored in proper storage cells/transistors.
The host logical address is often translated into intermediate terms of logical block and logical page addresses, where a logical block comprises a plurality of logical pages. There are various methods to perform this translation based on different flash memory controller implementations and algorithms. For example, the controller may map the upper host logical address bits to a logical block, and the rest of the lower host logical address bits to logical pages. The controller then maps the logical block and logical pages to physical block and physical pages. As an example, a logical block may be organized into 64 logical pages in sequential address order, such that logical block 0 is page-addressable from logical address 0 to 63, logical block 1 is page-addressable from logical address 64 to 127, logical block 2 is page-addressable from logical address 128 to 191, and so on. A logical block may be mapped to one or more physical blocks, and each logical page of this logical block may be mapped to a physical page of the mapped physical block(s). The controller then issues a sequence of low-level commands and control signals to read or write to flash memories using the mapped physical addresses. Host logical addresses and their corresponding terms of logical blocks and logical pages are virtual concepts, whereas physical blocks and physical pages are the real physical locations within flash memories.
Typically, the system volatile RAM 17 incorporated into the controller is used for storing the logical to physical address mapping and other system information. On power up, the controller is required to read mapping information from the flash memory 5 (typically in flash overhead data) and initialize the system volatile RAM 17 prior to any data transfer operation.
Other functions performed by the controller includes ECC (error correcting codes) generation and checking, error recovery, erasing blocks that contain obsolete data, performing wear-leveling function to improve on flash block usage, and others.
When a flash memory having multi-paged blocks is used, data in less than all the pages of a block is usually required to be updated by programming the new data in unused pages of either the same or another block. However, an efficient mapping algorithm for flash memories having multi-paged blocks has still not been satisfactorily developed. The following explains some of the fundamental challenges faced by a flash memory controller design for multi-paged block flash memory.
When a host writes N number of pages (where N≧1) of user data starting at a specific logical address to the storage device, the controller must implement some methods for mapping the logical address to flash physical address. The flash physical address is a function of the physical block number and physical page number. This address pair is herein denoted as {physical block, physical page}. The controller has to decide, for each of the N pages, in which {physical block, physical page} to store the user data. When the host subsequently reads data from the logical address previously written to, the controller must be able to translate the logical address to its mapped physical address, which is used to access specific location in flash memory and return the user data to the host.
Secondly, when the host updates M number of pages to the same logical address (where M≦N), the controller has to map the logical address to physical address for each of the M pages. The challenge is that a flash physical page must be erased before it can be written to again. Most present controllers implement methods to write user data to a different {physical block, physical page} than was previously written to for the same logical address. This requires the controller to re-map the logical address to a different {physical block, physical page} for each of the M pages for updates. When host subsequently reads data from the logical address, the controller must be able to translate the logical address to the physical address of the most recently written location to retrieve valid data, such that the older user data mapped to the same logical address are superseded.
Thirdly, host may be required to update to the same logical address multiple times, and each time with different user data from the previous writes.
Finally, when power for the non-volatile mass storage system is turned off and subsequently turned on again, the controller must be able to retain all the mapping information.
There are many controller designs to fulfill these functional requirements in order to make data access, storage, and transfer efficiently.
In a very early design, a host logical block is always mapped to a fixed flash physical block. In other words, every time the host writes to the same logical block, user data is always stored to the same flash physical block. However, prior to writing to the flash block, the flash block must first be erased. The disadvantage of this scheme is that any write is always slowed down by the time-consuming erase operation.
To address this, one prior art proposal was to avoid the “erase-before-write” scheme by re-writing user data to an erased physical block, and recording its associated logical block in the overhead data with a new flag. The previous data in the old block is marked using an old flag. In this scheme, the logical block number may be different from its mapped physical block number. However, for a flash memory having multi-paged blocks, the logical pages are always mapped to fixed physical pages within the block.
One disadvantage of this scheme is when host updates one or more pages of a logical block, a new erased physical block must be allocated for storing new data. Next, the valid pages of user data that were not over-written must be copied from the original block to the assigned erased physical block. The original physical block must then be invalidated by writing an old flag in its overhead data. Both the copying of pages and invalidating original block demand additional operation and time. Often times, the original block is invalidated even when not all the pages have been fully used, resulting in less efficient block usage. The more frequent block erase due to less efficient block usage will cause a drop in reliability since each flash block has limited program/erase cycles beyond which failure may occur. Additionally, the time consuming block erase may cause a performance penalty, even though it may be mitigated by performing erase in the background.
An improvement was made to avoid the copying of valid pages during updates. This is done by tagging the newly assigned erased physical block as a “moved” block. In fact, up to two physical blocks are used, one is the original block, and another is a moved block. Additional information is used to indicate whether a valid page is located in the original block, or the moved block. However, in this scheme, the logical pages are still associated with fixed physical pages within the blocks. Since the scheme has only one level of “moved” block, the process of copying valid pages and invalidating the “moved” block is still required when there are more than two updates to the same logical page. As before, this demands additional operation and time, results in less efficient block usage and more erase cycles to be performed.
In another attempt for flash controller design, the logical pages can be mapped to any physical pages within the mapped physical block. Hence, the logical to physical address mapping is done on a finer granularity. Tags in the overhead data associate a {logical block, logical page} with a {physical block, physical page}. To handle updates, instead of marking the original superseded page as old, the controller uses a time stamp written in the overhead data as an indication of which is the most recently written data. Two implementations are outlined. In both implementations, a physical block may be shared for data of different logical blocks.
In the first implementation, a time stamp is recorded in every physical page that was written. If a logical page is updated multiple times, user data will be stored in physical pages whose overhead data will have the same {logical block, logical page} tag but with different time stamps. On power up, for the controller to locate the most recently written page, it is expected that the controller reads the overhead data of all the flash physical pages, compares the logical addresses and time stamps to identify most recently written pages containing valid data.
In the second implementation, the controller is only required to record a time stamp for physical blocks instead of recording in every physical page. The time stamp is required to identify the one valid page, since, in its generalized form, data updates for same {logical block, logical page} may be written to pages of different physical blocks, and each physical block may also be shared with data of other logical blocks. The most recently written physical page is determined by the relative physical location within a block. The implementation requires a reverse reading technique to dynamically identify if a logical page has been re-written and generally requires a large buffer to re-assemble the user data prior to transferring them to the host in the correct order.
In both implementations, a real time clock or a modulo counter is required to generate a time value that is to be recorded in flash memory blocks or pages. This time stamping operation is expected to add complexity to the flash memory controller, such as having to generate time-stamp values, handling of wrap around cases, and to perform time-stamp comparison among pages having common logical addresses.
Another type of non-volatile memory that attracts much research attention is Non-Volatile Random Access Memory (NVRAM). Random Access Memory (RAM) is classified as volatile memory and has faster data access speed as it is based on a different type of technology and does not require erase-before-write operation. Currently, NVRAM is created by attaching a backup battery to a volatile random access memory. In this case, unlike a normal Random Access Memory (RAM), the data stored in a NVRAM is kept even if the external electric power supply (other than the battery) is switched off because the backup battery holds the electric charges required. RAM has much faster data transfer speed than ROM and the same applies to NVRAM.
Recently developed NVRAMs based on various technologies do not require the aid of a battery to keep stored data. These include Magneto-Resistive Random Access Memory (MRAM), Ferroelectric Random Access Memory (FRAM), Ovonic Unified Memory (OUM), and others currently under development. These solid-state memories are sometimes referred to as “next generation” or “universal” or “nano-technology” non-volatile memories and have properties similar to SRAM with additional feature of being non-volatile.
Similar to flash memory, these NVRAMs do not require power to retain data. There are however, major functional differences between flash memory and Non-Volatile Random Access Memory that provide NVRAM with advantages over flash memory as follows:                Contents in NVRAM are randomly addressable for read and write in minimum unit of a byte.        The process of writing and reading data in NVRAM is faster and it completes in one short read or write cycle. For flash memory, programming data will incur a long busy period during which time the state of the non-volatile memory cells are changed. For some flash implementation (e.g. NAND flash), reading data will incur a long busy period during which time the data from non-volatile memory cells are read.        Updating a specific byte location in NVRAM can be performed multiple times and it does not require erasing that byte prior to the update.        Writing any byte is allowed at any address with no limitations on the allowable address due to prior history of writes, unlike some flash memory (e.g. NAND flash) that imposes restrictions on programming in sequential page addresses within a block.        
The term NVRAM as used here encompasses any solid-state non-volatile random access memory having at least some functional characteristics (preferably all) as described above, including MRAM, FRAM, OUM and others based on various technologies, some of which are still under research and development. The disadvantage of NVRAM is that at the current time, it is still more expensive than flash memory in terms of cost per MB. Hence, it is not expected to completely replace flash memory as the non-volatile memory of choice in mass storage applications in the near future.
Ongoing design and manufacturing improvements are bringing NAND flash memory to the next level of performance. Process shrinks are providing flash memory devices with multi-gigabit storage densities as well as faster read access. In addition, architectural innovations are boosting the speeds of erasure and programming as well as read access. These improvements have provided a roadmap that will bring NAND flash performance to new levels that further increase their utility in modern computing system designs.